package leetcode_2401_2500;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

public class LeeCode_2434 {
    public static void main(String[] args) {
        System.out.println(robotWithString("bac"));
    }
    private static String robotWithString(String s) {
        int n = s.length();
        char[] mines = new char[n];
        char min = 'z';
        for(int i = n - 1; i >= 0; i--){
            mines[i] = (char) Math.min(min, s.charAt(i));
            min = mines[i];
        }
        LinkedList<Character> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            while (!queue.isEmpty() && mines[i] >= queue.peek()){
                sb.append(queue.poll());
            }
            queue.addFirst(s.charAt(i));
        }
        while (!queue.isEmpty()){
            sb.append(queue.poll());
        }
        return sb.toString();
    }
}
